package pers.whj.sort;

public class QuickSort<T> extends Sort<T> {
    public QuickSort(T[] data) throws SortException {
        super(data);
    }

    public QuickSort(T[] data, Compare<T> compare) throws SortException {
        super(data, compare);
    }

    @Override
    public void sort(int left, int right) throws SortException {
        sort(mData, mCompare, left, right);
    }

    public static <E> void sort(E[] data) throws SortException {
        sort(data, null);
    }

    public static <E> void sort(E[] data, Compare<E> compare) throws SortException {
        sort(data, compare, 0, data == null ? 0 : data.length - 1);
    }

    public static <E> void sort(E[] data, Compare<E> compare, int left, int right) throws SortException {
        check(data, compare, left, right);
        quickSort(data, compare, left, right);
    }

    private static <E> void quickSort(E[] data, Compare<E> compare, int left, int right) {
        if (left < right) {
            int pivotPosition = partition(data, compare, left, right);
            quickSort(data, compare, left, pivotPosition - 1);
            quickSort(data, compare, pivotPosition + 1, right);
        }
    }

    private static <E> int partition(E[] data, Compare<E> compare, int left, int right) {
        int k = (left + right) / 2;
        E temp = data[left];
        data[left] = data[k];
        data[k] = temp;
        E pivot = data[left];
        while (left < right) {
            while (left < right && !compare.swap(pivot, data[right])) {
                right--;
            }
            data[left] = data[right];
            while (left < right && compare.swap(pivot, data[left])) {
                left++;
            }
            data[right] = data[left];
        }
        data[left] = pivot;
        return left;
    }
}